package com.javabasic.algorithm.leetcode;

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [662. Maximum Width of Binary Tree](https://leetcode.cn/problems/maximum-width-of-binary-tree/)
 * @since Created by work on 2022/8/27 19:09
 */
public class MaximumWidthOfBinaryTree {

    /**
     * 内存超出限制
     * @param root
     * @return
     */
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int result = 0, queueSize, left = 0, right = 0;
        TreeNode currentNode;
        boolean isBreak;

        int nullNum;

        while (!queue.isEmpty()) {
            queueSize = queue.size();
            isBreak = true;

            nullNum = 0;
            for (int i = 0; i < queueSize; i++) {
                currentNode = queue.poll();

                if (isBreak && currentNode == null) {
                    continue;
                }

                if (currentNode == null) {
                    nullNum++;
                } else {
                    for (int j = 0; j < nullNum; j++) {
                        queue.offer(null);
                        queue.offer(null);
                    }
                    nullNum = 0;

                    queue.offer(currentNode.left);
                    queue.offer(currentNode.right);
                    if (isBreak) {
                        left = i;
                    }
                    right = i;
                    isBreak = false;
                }
            }
            if (isBreak) {
                break;
            } else {
                result = Math.max(result, right-left+1);
            }
        }

        return result;
    }



    public int widthOfBinaryTree2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<Node662> queue = new LinkedList<>();
        queue.add(new Node662(root, 0));

        int result = 0, queueSize, len, nullNum;
        Node662 currentNode;

        while (!queue.isEmpty()) {
            queueSize = queue.size();
            len = 0;
            nullNum = 0;

            for (int i = 0; i < queueSize; i++) {
                currentNode = queue.poll();

                len += currentNode.getLen();

                if (currentNode.getNode() == null) {
                    nullNum++;
                    continue;
                }


                if (currentNode.getNode().left != null) {
                    queue.offer(new Node662(currentNode.getNode().left, currentNode.getLen() * 2));
                }
                if (currentNode.getNode().right != null) {
                    if (currentNode.getNode().left != null) {
                        queue.offer(new Node662(currentNode.getNode().right, 0));
                    } else if (len == 0) {
                        queue.offer(new Node662(currentNode.getNode().right, 0));
                    } else {
                        queue.offer(new Node662(currentNode.getNode().right, currentNode.getLen() * 2 + 1));
                    }
                }


            }

            result = Math.max(result, len + queueSize);

            System.out.println(result);

        }

        return result;
    }
}

class Node662 {
    private TreeNode node;
    private int len;

    public Node662(TreeNode node, int len) {
        this.node = node;
        this.len = len;
    }

    public TreeNode getNode() {
        return node;
    }

    public void setNode(TreeNode node) {
        this.node = node;
    }

    public int getLen() {
        return len;
    }

    public void setLen(int len) {
        this.len = len;
    }
}


